import java.util.List;
import java.util.Stack;

public class BinaryTree {
    static class TreeNode{
        private TreeNode left;
        private TreeNode right;
        private int var;

        public TreeNode(int var) {
            this.var = var;
        }
    }
    public int preIndex;
    public int postIndex;
    public  TreeNode buildChilidTree(int[] preorder,int[] inorder,int inbegin,int inend){
            if(inbegin>inend){
                return null;
            }

            TreeNode root=new TreeNode(preorder[preIndex]);
            int rootIndex=findRoot(inorder,inbegin,inend,preorder[preIndex]);
            preIndex++;
            root.left=buildChilidTree(preorder,inorder,inbegin,rootIndex-1);
            root.right=buildChilidTree(preorder,inorder,rootIndex+1,inend);
            return root;


    }
    private int findRoot(int[]inorder,int inbegin,int inend,int key){
        for (int i = inbegin; i <= inend; i++) {
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
    public  TreeNode buildChilidTree_(int[] postorder,int[] inorder,int inbegin,int  inend){
        if(inbegin>inend){
            return null;
        }

        TreeNode root=new TreeNode(postorder[postIndex]);
        int rootIndex=findRoot(inorder,inbegin,inend,postorder[postIndex]);
        postIndex--;
        root.right=buildChilidTree_(postorder,inorder,rootIndex+1,inend);
        root.left=buildChilidTree_(postorder,inorder,inbegin,rootIndex-1);

        return root;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if(p==root||q==root){
            return root;
        }
        if(root==null){
            return null;
        }
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null){
            return leftTree;
        }else{
            return rightTree;
        }

    }
    private void tree2strChild(TreeNode t,StringBuilder s){
        if(t==null){
            return ;
        }
        s.append(t.var);
        if(t.left!=null){
            s.append("(");
            tree2strChild(t.left,s);
            s.append(")");
        }else{
            return ;
        }
        if(t.right!=null){
            if(t.left==null){
                s.append("()");
            }
            s.append("(");
            tree2strChild(t.right,s);
            s.append(")");
        }else{
            return ;
        }


    }
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder=new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void preorderTraversal(TreeNode root){
        TreeNode cur=root;
        Stack<TreeNode>stack=new Stack<>();
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                System.out.print(cur.var+" ");
                cur=cur.left;
            }
            TreeNode tmp=stack.peek();
            cur=tmp.right;
            stack.pop();
        }
    }
    public void inorderTraversal(TreeNode root){
        TreeNode cur=root;
        Stack<TreeNode>stack=new Stack<>();
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode tmp=stack.peek();
            System.out.print(tmp.var+" ");
            cur=tmp.right;
            stack.pop();
        }
    }
    public void postorderTraversal(TreeNode root){
        Stack<TreeNode>stack=new Stack<>();
        TreeNode prev=null;
        TreeNode cur=root;
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;

            }
            TreeNode top=stack.peek();
            if(top.right==null||prev==top.right){
                System.out.print(top.var+" ");
                stack.pop();
                prev=top;
            }else{
                cur=top.right;
            }

        }
    }

}
